#include<stdlib.h>
#include<stdio.h>
#include<string.h>
typedef struct node{
	int w;
	char c;
	struct node  *l;
	struct node  *r;
	char encode[20];
}Node;
typedef struct n{
	char c;
	char code[20];
}N;
void decode(char ch[],int start,int length,Node * root);void encode(char str[],N *  n[]);
void order_node(Node *h[] , int length);
void getCode(char c,N * n[]);
Node *init_huffman();
Node *create_node(char name,int weighte);
void init_n(Node * root,N * n[]);
void display(Node * root);
void order_node(Node * h[],int length){
	for(size_t i = 0; i < length-1; ++i){
		for(size_t j = i + 1; j < length; ++j){
			if(h[i]->w < h[j]->w){
				Node * temp;
				temp = h[j];
				h[j] = h[i];
				h[i] = temp;
			}
		}
	}
}
//a 7 b 19 c 2 d 6 e 32 f 3 g 21 k 10
Node *init_huffman(){
	Node * h[8];
	h[0] = create_node('a',7);
	h[1] = create_node('b',19);
	h[2] = create_node('c',2);
	h[3] = create_node('d',6);
	h[4] = create_node('e',32);
	h[5] = create_node('f',3);
	h[6] = create_node('g',21);
	h[7] = create_node('k',10);
	order_node(h,8);
	int loop = 8;
	while(loop>1){
		Node * temp = (Node*)malloc(sizeof(Node));
		temp->c = '0';
		temp->w = h[loop-1]->w+h[loop-2]->w;
		temp->l = h[loop-1];
		temp->r = h[loop-2];
		strcpy(temp->encode,"");
		h[loop-2] = temp;
		h[loop-1] = NULL;
		--loop;
		order_node(h,loop);
	}
	return h[0];

}

Node * create_node(char name,int weight){
	Node *node=(Node*)malloc(sizeof(Node));
	node->c = name;
	node->w = weight;
	strcpy(node->encode,"");
	node->l = NULL;
	node->r = NULL;
	return node;
}
int main(){
	Node * huffman_root = init_huffman();
	display(huffman_root);
	N *n[8]={NULL};
	init_n(huffman_root,n);
	for(int i = 0; i< 8; ++i)
		printf("%c---%s\n",n[i]->c,n[i]->code);
	encode("abc",n);
	printf("\n");
	char message[] = "1100";
	decode(message,0,4,huffman_root);
}

void init_n(Node * root,N * n[]){

	if(root->c!='0'){
		N * temp  = (N*)malloc(sizeof(N));
		temp->c = root->c;
		strcpy(temp->code,root->encode);
		for(int i = 0 ; i < 8; ++i){
			if(n[i]!=NULL)
				continue;
			n[i]=temp;
			break;
		}	
	}
	if(root->l!=NULL){
		init_n(root->l,n);
		init_n(root->r,n);
	}
}

void display(Node * root){
	if(root->c!='0')

		printf("%c---%d---%s\n",root->c,root->w,root->encode);
	if(root->l!=NULL){
		strcat(root->l->encode,root->encode);
		strcat(root->l->encode,"0");
		strcat(root->r->encode,root->encode);
		strcat(root->r->encode,"1");
		display(root->l);
		display(root->r);
	}
}



void encode(char str[],N * n[]){
	size_t i = 0;
	while(str[i]){
		getCode(str[i],n);
		i++;
	}
}

void getCode(char c,N * n[]){
	for(size_t i = 0 ; i < 8; ++i){
		if(c==n[i]->c){
			printf("%s",n[i]->code);
			break;
		}
	}
}


void decode(char ch[],int start,int length,Node * root){
	Node * temp = root;
	for(size_t i = start ; i < length; i++){
		if(ch[i] == '0')
			temp = temp->l;
		else
			temp= temp->r;
		if(temp->c!='0'){
			printf("%c",temp->c);
			if(i+1==length)
				break;
			decode(ch,i+1,length,root);
			break;
		}
	}
}
